package 代码随想录_回溯.力扣_回溯.搜索矩阵.牛客;

import java.util.Scanner;

/**
 * day_42
 * @author zx
 * @create 2022-08-22 13:01
 */
public class 走迷宫 {
    /**
     * 这个是最难的
     */
    private static int res = Integer.MAX_VALUE;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            res = Integer.MAX_VALUE;
            char[][] arr = new char[10][10];
            for(int i = 0;i < 10;i++){
                String str = sc.nextLine();
                for(int j = 0;j < 10;j++){
                    arr[i][j] = str.charAt(j);
                }
            }
            boolean[][] used = new boolean[10][10];
            dfs(arr,0,1,0,used);
            System.out.println(res);
        }
    }
    //res存放最短路径,path存放当前路径
    private static void dfs(char[][] arr, int i, int j, int path, boolean[][] used){
        if(i < 0 || i >= 10 || j < 0 || j >= 10){
            return;
        }
        if(arr[i][j] == '#' || used[i][j]){
            return;
        }
        if(path > res){
            return;//这个地方的剪枝很关键!!! 在路径很多的时候,可以有效的防止多余的计算
        }
        if(i == 9 && j == 8){
            if(path < res){
                res = path;
            }
            return;
        }
        used[i][j] = true;
        dfs(arr,i - 1,j,path + 1,used);
        dfs(arr,i + 1,j,path + 1,used);
        dfs(arr,i,j - 1,path + 1,used);
        dfs(arr,i,j + 1,path + 1,used);
        used[i][j] = false;
    }
}
